package offerv1;

import java.util.ArrayList;
import java.util.List;

public class Offer34 {

    private List<List<Integer>> ans;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        ans = new ArrayList<>();
        dfs(root, target, new ArrayList<>(), 0);
        return ans;
    }

    public void dfs(TreeNode node, int target, List<Integer> router, int sum) {
        if (node == null) {
            return;
        }

        router.add(node.val);
        sum += node.val;
        if (sum == target && node.left == null && node.right == null) {
            ans.add(new ArrayList<>(router));
        }

        dfs(node.left, target, router, sum);
        dfs(node.right, target, router, sum);
        router.remove(router.size() - 1);
    }
}
